package com.wzh.test.dynamicprograming;

import java.util.Arrays;

/**
 * 已知数组{3,34,4,12,5,2}
 * 问 有没有这样的方案：
 * 数组中的两个值加起来=9
 * 如果存在，返回true,否则返回false
 */

public class Demo2 {

    public static int[] arr = {3, 34, 4, 12, 5, 2};

    public static void main(String[] args) {
//        boolean result = isExists();
//        System.out.println(result);
//
//        boolean result2 = recSubset(arr.length - 1,9);
//        System.out.println(result2);

        System.out.println(dpSubset(9));
        System.out.println(dpSubset(10));
        System.out.println(dpSubset(11));
        System.out.println(dpSubset(12));
        System.out.println(dpSubset(13));
        System.out.println(dpSubset(14));
    }

    /**
     * 很明显 4+5=9，这是人眼看出来的，如果数组很大很大，人眼就看不出来了
     * 计算机很笨，更加看不出来，只能一个一个尝试，那就简单了
     * <p>
     * 这个方法实现了，符合计算思维，但是效率很低，时间复杂度=O(N²)
     * 有没有更好的办法呢？
     */
    public static boolean isExists() {
        boolean exist = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == 9) {
                    exist = true;
                    break;
                }
            }
            if (exist) {
                break;
            }
        }

        return exist;
    }

    /**
     * 动态规划 利用subset思想，我们要的是subset(arr.leng-1,9)是否存在
     * 然后往下判断，是否存在subset(i-1,7) or sub(i-1,9)存在，依次递归
     * 递归出口：s=0 || i = 0 && arr[i] != s
     *
     * @return
     */
    public static boolean recSubset(int i, int sum) {
        if (sum == 0) {
            return true;
        }
        if (i == 0) {
            return arr[i] == sum;
        }
        if(arr[i] > sum){
            return recSubset( i - 1,sum);
        }else {
            return recSubset(i - 1, sum - arr[i]) || recSubset(i - 1, sum);
        }
    }

    /**
     * 上面使用的是递归方法，递归效率比较低，试试非递归
     * 定义一个二维数组int[arr.length][sum+1]
     * 把第0列都设置为false,把第0行都设置为false,再把第0行第int[0]列设置为true,再把第n行第0列设置为true
     * 循环设置每一个单元格，直到最后
     */
    public static boolean dpSubset(int sum){
        boolean[][] subSet = new boolean[arr.length][sum + 1];
        for(int i = 1; i < subSet.length;i++){
            subSet[i][0] = true;
        }
        subSet[0][arr[0]] = true;

        for(int i = 1;i < arr.length;i++){
            for(int j = 1;j <= sum;j++){
                if(j < arr[i]){
                    subSet[i][j] = subSet[i-1][j];
                }else {
                    subSet[i][j] = subSet[i - 1][j - arr[i]] || subSet[i - 1][j];
                }
            }
        }
        return subSet[arr.length - 1][sum];
    }
}
